import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 978. 最长湍流子数组
 * https://leetcode-cn.com/problems/longest-turbulent-subarray/
 */
public class Solutions_978 {
    public static void main(String[] args) {
        int[] arr1 = {9, 4, 2, 10, 7, 8, 8, 1, 9};  // output: 5  解释：(A{1} > A{2} < A{3} > A{4} < A{5})
        int[] arr2 = {4, 8, 12, 16};  // output: 2
        int[] arr3 = {100};  // output: 1

        List<int[]> inputs = new ArrayList<>();
        inputs.add(arr1);
        inputs.add(arr2);
        inputs.add(arr3);

        for (int[] input : inputs) {
            int result = maxTurbulenceSize(input);
            System.out.println(result);
        }
    }

    /**
     * 解法二：动态规划（7ms）
     */
    public static int maxTurbulenceSize(int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        } else if (arr.length == 1) {
            return 1;
        } else if (arr.length == 2) {
            return arr[0] == arr[1] ? 1 : 2;
        }
        int len = arr.length;
        // dp[4] = 5，表示以 nums[4] 结尾可以形成湍流子数组的最大长度是 5
        int[] dp = new int[len];
        int res = 1;

        for (int i = 1; i < len; i++) {
            if (i > 1 && ((arr[i - 1] < arr[i] && arr[i - 1] < arr[i - 2]) ||
                    (arr[i - 1] > arr[i] && arr[i - 1] > arr[i - 2]))) {
                // 大-小-大 或者 小-大-小 形式
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = arr[i] == arr[i - 1] ? 1 : 2;
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    /**
     * 解法一：动态规划（6ms）
     * 交叉
     */
    public static int maxTurbulenceSize2(int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        int len = arr.length;
        int res = 1;
        // maxDp[4] = 5，表示 nums[4] > nums[3]，且以 nums[4] 结尾的湍流子数组，最大长度为 5
        // 因为 nums[4] > nums[3]，所以记录在 maxDp 里，否则记录在 minDp 中
        int[] minDp = new int[len];
        int[] maxDp = new int[len];
        // 设定初始值
        Arrays.fill(minDp, 1);
        Arrays.fill(maxDp, 1);

        for (int i = 1; i < len; i++) {
            if (arr[i] > arr[i - 1]) {
                // 大于前一元素时，那么前一元素要小于其前一元素才能形成湍流子数组（大-小-大）
                maxDp[i] = minDp[i - 1] + 1;
                res = Math.max(res, maxDp[i]);
            } else if (arr[i] < arr[i - 1]) {
                // 小于前一元素时，那么前一元素要大于其前一元素才能形成湍流子数组（小-大-小）
                minDp[i] = maxDp[i - 1] + 1;
                res = Math.max(res, minDp[i]);
            }
        }
        return res;
    }
}
